"""
编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

输入: 6
输出: true
解释: 6 = 2 × 3

使用递归的方法从2 3 5 里面取数据然后不断递归判断
"""

class Solution:
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num < 2:
            return num == 1
        elif num % 5 == 0:
            return self.isUgly(num / 5)
        elif num % 3 == 0:
            return self.isUgly(num / 3)
        elif num % 2 == 0:
            return self.isUgly(num / 2)
        else:
            return False

    def dd(self):
        n = int(input())
        dp = [1, 2, 3, 4, 5]
        def findmin(l, k):
            res = min(filter(lambda x: x > l[-1], [a * k for a in l]))
            return res
        if n < 5:
            print(dp[n - 1])
        else:
            while len(dp) < n:
                cur = min(findmin(dp, 2), findmin(dp, 3), findmin(dp, 5))
                dp.append(cur)
            print(dp[-1])